package leetCode.offer26;

/**
 * 输入两棵 二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 */
public class Solution1 implements Solution{


    /**
     *
     * 实现思路：
     *  遍历A树节点，找到和B树根节点相等的节点cur，
     *  然后遍历B树，比对B树root开始和A树cur开始，以相同的规则遍历比较：
     *     如果存在B树的遍历节点和A树遍历节点不相等，则退出比较，接着遍历A树寻找和B树root相等的节点
     *     否则接着遍历B树，直到B树遍历完，这时返回true
     * @param A
     * @param B
     * @return
     */
    @Override
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B==null||A==null)
            return false;
        return deepIteratorOne(A,B);
    }


    /**
     * 比较root1是否是root2的子树
     * @param root1
     * @param root2
     */
    public static boolean deepIterator(TreeNode root1,TreeNode root2) {
        if(root1 == null) {
            return true;
        }
        if(root2 == null){
            return false;
        }
        System.out.print(root1.val+" ");
        if(root1.val!=root2.val){
            return false;
        }
        boolean left = deepIterator(root1.left,root2.left);
        boolean right = deepIterator(root1.right,root2.right);
        return left&&right;
    }


    /**
     * 递归root树，如果存在和sub相同的节点，则比较两棵树
     * @param root
     * @param sub
     * @return
     */
    public static boolean deepIteratorOne(TreeNode root,TreeNode sub) {
        if(root==null) {
            return false;
        }
        boolean result = false;
        //比较他们的节点是否一样
        if(root.val==sub.val){
            result = deepIterator(sub,root);
        }
        if(result) return true;
        return deepIteratorOne(root.left,sub)|| deepIteratorOne(root.right,sub);
    }


}
